#include <dbg.h>
#include <gtest/gtest.h>

using namespace std;

class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<vector<int>> res;

        vector<int> path;
        dfs(graph, 0, path, res);

        return res;
    }

private:
    void dfs(vector<vector<int>>& graph,
             int step,
             vector<int>& path,
             vector<vector<int>>& res) {
        path.push_back(step);  // 在访问节点时立即记录

        if (step == graph.size() - 1) {
            res.push_back(path);
        } else {
            for (auto& node : graph[step]) {
                dbg(path);
                dfs(graph, node, path, res);
            }
        }

        path.pop_back();  // 关键修改：回溯时移除当前节点
    }
};

TEST(TEST1, allPathsSourceTarget) {
    Solution s;

    vector<vector<int>> graph{{1, 2}, {3}, {3}, {}};
    vector<vector<int>> res{{0, 1, 3}, {0, 2, 3}};
    EXPECT_EQ(s.allPathsSourceTarget(graph), res);
}

TEST(TEST2, allPathsSourceTarget) {
    Solution s;

    vector<vector<int>> graph{{4, 3, 1}, {3, 2, 4}, {3}, {4}, {}};
    vector<vector<int>> res{
        {0, 4}, {0, 3, 4}, {0, 1, 3, 4}, {0, 1, 2, 3, 4}, {0, 1, 4}};
    EXPECT_EQ(s.allPathsSourceTarget(graph), res);
}

int main(int argc, char** argv) {
    ::testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}